/*
 * Nancy Qiannan Zhang
 * Andrew ID: qiannanz
 * 
 * Mita Yipeng Yun
 * Andrew ID: yipengy
 */

package edu.cmu.cs211.bacon.util;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Hashtable;
import java.util.List;
import java.util.PriorityQueue;

/**
 * An implementation of graph search based on Dijkstra. Does not handle negative edges.
 */
public class Dijkstra implements GraphSearch {

	
	/**
	 * @throws IllegalArgumentException
	 *             if g has negative edge weights.
	 */
	@SuppressWarnings("unchecked")
	public <V,E extends Edge<V>> List<E> shortestPath(Graph<V,E> g, V start, V finish)
	{
		if(g == null || start == null || finish == null)
			throw new NullPointerException();
		
		/*
		 * result table:
		 * key: vertex
		 * value: arraylist of paths from start to this vertex
		 */
		Hashtable<V, ArrayList<Edge<V>>> result = new Hashtable<V, ArrayList<Edge<V>>>();
		
		// distance hashtable: store the shortest distance from start to current key
		final Hashtable<V, Double> distance = new Hashtable<V, Double>();
		
		// comparator based on distance: to be used by pq
		Comparator<V> comp = new Comparator<V>()
		   {
			   @Override
			   public int compare(V arg0, V arg1) {
				   return (int) (distance.get(arg0) - distance.get(arg1));
			   };
		   };

		// priority queue to keep track of all vertices and update the distance table
		PriorityQueue<V> q = new PriorityQueue<V>(11, comp);
		
		/* initialization */
		// set d(s) = 0, others to infinite, insert all into pq */
		
		// add all vertices to a new set
		ArrayList<V> vertices = new ArrayList<V>(g.vertices());
		
		// iterate thru the set, insert everything to pq and distance table
		for(V v: vertices)
		{
			if(v.equals(start))
			{
				// distance of start = 0
				distance.put(v, (double) 0);
				q.add(v);
				// for s: just put an empty list in the result
				result.put(v, new ArrayList<Edge<V>>());
			}
			else
			{
				// distance of other vertices are initialized to infinite
				distance.put(v, Double.MAX_VALUE);
				q.add(v);
			}
		}
		
		/* continue */
		while(!q.isEmpty())
		{
			// delete the min element from pq
			V current = q.poll();
			
			// update distance table for each neighbor of current
			ArrayList<V> nbs = new ArrayList<V>(g.neighbors(current));
			for(V v: nbs)
			{
				// it should only look at elements that haven't been polled
				if(q.contains(v)){
				// edge from current to v
				Edge<V> edge = (Edge<V>) g.connected(current, v);
				if(edge.weight() < 0)
					throw new IllegalArgumentException();
				// new distance
				double newD = edge.weight() + distance.get(current);
				
				if(distance.get(v) > newD)
				{
					// update distance table for v
					distance.remove(v);
					distance.put(v, newD);
					
					// update result
					if(current.equals(start))	// current node is start
					{
						//make a new list
						ArrayList<Edge<V>> list2 = new ArrayList<Edge<V>>();
						// add this new edge to the new list
						list2.add(edge);
						// if v already exists, remove first
						if(result.get(v)!= null)
							result.remove(v);
						result.put(v, list2);
					}
					else
					{
						// get previous list first
						ArrayList<Edge<V>> list = result.get(current);
						// make a new list identical to the prev list
						ArrayList<Edge<V>> list2 = new ArrayList<Edge<V>>(list);
						// add the new edge to the new list
						list2.add(edge);
						// if v already exist, remove first
						if(result.get(v)!= null)
							result.remove(v);
						result.put(v, list2);
					}
				}
				// update priority queue
				q.remove(v);
				q.offer(v);
				}
			}
		}
		
		// return the result from result hashtable
		return (List<E>) result.get(finish);
	}
	
	
}
